n=996;
S=[1,897,1315,2217,2705,3039,3139,3980,4533,4768,5062,5572,5784,6037,6042,6379,6675,7298,8288,8668,8862,8915,9443,10368,10860,10961,11484,11965,12838,12888,13307,14113,15060,15897,16325,16761,16933,17461,18458,19183,19665,19957,20911,21325,21870,22830,23581,24422,24725,25186,26126,26623,27138,27327,27469,28195,28485,29151,29359,29523,30239,30585,31274,31938,32122,32240,33060,33135,33500,34318,34838,35686,36515,36990,37971,38065,38220,38953,39607,40065,40261,40856,41530,41960,42463,43280,44155,44667,45151,45953,46349,47268,47418,47504,47808,47861,48784,48909,49038,49046,49708,50076,50651,50862,51705,52262,52567,53285,53296,54255,54432,55357,55631,56483,56839,57617,58006,58238,58248,59121,59156,59562,60355,61258,61470,61568,62525,63379,64320,65125,65987,66591,66765,66923,67738,68474,69189,70028,70483,71209,72008,72641,73293,73368,73573,74300,74872,75466,76144,76726,76913,77346,78054,79034,79371,80010,80808,81103,81597,82337,82438,82514,82579,83572,83806,84405,85136,85805,86245,86432,86547,87505,88325,88812,88846,89590,89805,90130,90469,91363,91990,92235,92282,92618,93563,93947,94641,95385,95784,95973,96177,96396,96661,97648,97862,98081,98388,99052,99940,100406,101257,101261,101686,102078,102569,103029,103166,103592,104096,104292,104332,104464,104905,104992,105179,105285,105475,106356,107206,107514,108303,109077,109605,109661,110142,110603,111596,112384,112510,113392,113647,114624,115229,115910,115999,116815,117675,117902,118145,118229,118371,118654,118871,119173,119262,119385,119794,120073,120079,121057,121645,122159,122912,123747,124036,124990,125006,125289,125751,126611,127495,128213,128770,129261,129380,130027,130054,130752,131626,131896,132678,133413,133685,134403,134441,134802,135644,136091,136450,137017,137444,138110,138192,139091,139593,139965,140538,140775,141149,141186,141284,141544,142018,142674,143144,143737,144041,144538,144549,145446,146213,146725,147358,148116,148348,148738,149576,150369,150926,151842,152203,152906,153490,153652,154255,155060,155313,155491,155535,156163,157096,157956,158844,159252,159769,160128,160130,160670,161526,162257,162695,163038,163282,164072,164892,165368,166268,166927,167197,167655,167950,168300,169180,170059,170572,171056,171461,171946,172327,172495,172609,172643,172672,172675,173117,173383,173464,173627,174433,175089,175983,176947,176947,177087,177561,178100,178435,178810,179727,180052,180604,180818,181212,181645,181739,182365,183002,183220,183333,184070,184456,184683,185455,185871,186820,187035,187717,187748,187846,188335,189023,190015,190188,190595,191446,192094,193041,193947,194689,195554,196504,196519,196599,196944,197111,198004,198976,199780,199892,199978,200240,200739,200771,201524,202439,203420,204388,204705,204719,205504,206029,206731,207510,208209,208319,208669,208736,209512,209769,210578,211221,211429,211972,212414,212687,213398,213734,213980,214215,214664,214715,215212,215879,215962,216213,216515,217299,218238,218857,219655,220380,220525,220745,220969,221532,221581,222156,222786,223612,224163,224323,224512,225272,225975,226606,226640,227055,227742,228740,229391,229528,230296,231163,231967,232818,233656,233763,234118,234896,235341,236213,236436,237026,237119,237567,237722,238583,239325,239829,240236,240530,241194,241509,242282,242370,243316,243842,244345,244979,245504,246377,246867,246880,247341,247355,248220,248520,249359,250298,251095,251380,252193,252932,253527,254152,254340,254809,255296,255945,256637,257250,257913,258271,259199,259636,260082,260677,261641,262309,262539,262748,263010,263450,263673,264396,264569,265376,266118,266132,266598,267138,267156,267436,267716,268048,268954,269142,269943,270056,270612,271107,271553,271773,272345,272720,273378,274115,275085,275427,275833,276753,277023,277410,277490,277702,277813,278066,278804,279376,279643,279849,279962,279967,280172,280285,280622,280734,280754,281612,282556,282851,282924,283315,283831,284476,285242,286135,286518,286975,287929,288437,288534,289477,290373,290550,290707,291433,291582,292196,292496,292913,293733,293865,294006,294751,294996,295474,296331,297314,297651,298172,298452,298862,299774,300289,301063,301462,301871,302029,302604,302968,303354,304026,304334,304617,305185,305369,306097,306814,307613,307642,308495,308834,308996,309990,310075,310201,310394,311056,311167,311697,311881,311991,312651,313467,314092,314527,315461,315496,315809,316319,316437,317136,318037,318182,318883,319353,319402,319832,320738,321586,321765,322245,323151,323492,323967,324678,324864,325532,325625,325641,326559,327554,327680,328259,328790,329260,329993,330459,330683,330730,331706,332048,332513,333110,333317,333484,333552,333808,334125,334819,335642,336138,336313,336762,337318,337687,337848,338590,338629,339601,340360,341036,342005,342609,342865,343366,343442,344431,345399,345699,346455,347119,347481,347703,347966,348535,348644,348694,349519,349664,350127,350776,351136,351774,351873,352789,352798,353777,354155,354921,355873,356729,357172,357813,358275,358693,358837,359375,359502,360333,360890,361773,361988,362907,363014,363492,363981,364915,365163,365197,365277,365988,366390,366830,367181,367402,367478,367557,367758,368212,369057,369929,369960,369968,370483,370976,371402,371780,372530,372802,373012,373039,373196,373340,374287,375269,375892,376048,376965,377555,378464,379180,379482,379794,379951,380323,380856,381807,382258,382711,383117,383133,383179,383616,384358,384919,385568,385737,386395,386514,386675,387262,387409,387727,388458,388553,388854,388928,389897,390834,391498,392377,393031,393998,394191,394721,394780,395225,395707,396218,396836,397443,397689,398353,399117,400106,401050,401183,402060,402663,402916,402955,403146,403546,403622,404544,404758,404854,405851,406035,406069,406450,406515,406922,407271,408247,408903,409312,409453,410310,410949,411708,412174,412778,413202,414151,414745,415114,415197,415389,416080,416135,416366,417248,417703,418011,418536,419205,419609,419851,420424,420582,421205,421562,421846,422538,422591,423532,424352,424546,425345,425524,426197,427181,427964,428780,429714,430093,430998,431735,432025,432622,433414,433935,434416,435383,435931,436656,437012,437684,438651,439580,440410,440720,440726,440841,440844,440903,441678,442220,443192,443487,444208,444854,445134,445640,445822,446756,447360,447448,448120,449014,449700,449884,450019,450905,451775,452178,452509,452737,452813,453112,453988,454613,454941,455824,456283,456334,456995,457231,457824,458177,458708,458743,459461,459991,460251,461152,461617,462481,463470,464326,464804,465199,465959,466291,466573,467204,467939,468552,469130,469660,470291,470747,470903,471863,471922,472538,473268,473707,474278,474602,475395,476216,476294,476806,477158,477496,477910,478728,479649,479773,480167,480567,481086,481241,481693,482214,482720,483626,484479,484564,485002,485488,486029];
A=[314,167,320,649,897,760,221,940,554,730,306,166,805,974,464,779,45,374,254,468,243,782,232,290,455,602,895,991,645,50,831,252,607,28,991,76,163,591,893,120,604,397,520,987,223,760,758,555,989,244,211,133,180,465,622,989,475,197,946,537,51,36,74,297,159,768,312,146,867,783,277,891,753,748,231,662,686,891,463,236,227,337,113,123,713,758,990,539,834,683,215,320,728,257,35,345,502,59,236,930,861,437,681,279,219,756,297,135,638,284,688,104,983,209,477,235,817,964,714,597,338,528,110,483,452,15,494,819,763,391,459,810,787,55,227,952,226,206,598,688,157,533,124,385,404,684,850,81,495,535,635,8,845,108,318,768,213,491,753,447,189,894,139,520,380,222,527,539,37,584,466,126,735,734,823,951,2,649,442,809,110,457,711,321,727,732,916,34,912,541,632,16,30,191,123,757,82,461,290,937,618,232,788,831,937,546,915,103,214,884,111,809,659,526,155,750,585,455,508,488,150,656,909,103,413,324,976,578,976,719,523,324,715,98,5,57,118,613,595,764,776,808,297,503,91,332,41,908,307,777,379,263,787,579,290,257,558,7,520,750,820,682,65,821,17,370,466,139,330,546,596,313,786,188,311,446,859,857,294,156,109,797,386,384,906,222,118,771,449,696,651,752,286,175,343,455,67,486,720,408,254,567,941,62,440,718,516,915,389,822,177,686,868,521,73,237,287,334,572,716,224,518,65,237,823,124,645,626,773,748,598,803,322,188,232,53,879,281,487,366,859,304,268,767,914,270,39,147,94,311,123,910,953,392,628,638,407,208,618,894,314,452,872,456,313,516,182,642,493,67,78,400,403,587,371,616,363,386,479,908,622,804,308,121,454,541,167,97,852,363,718,255,142,915,258,581,213,152,623,287,826,741,174,453,233,70,403,73,142,834,604,905,1,210,564,134,658,407,427,216,516,742,859,592,130,16,573,43,800,374,6,464,515,70,766,357,79,529,57,415,892,276,787,303,379,813,805,394,55,578,832,267,861,644,411,859,294,720,260,262,753,673,928,322,379,939,59,561,728,178,590,184,828,577,320,649,670,943,211,81,888,897,129,61,485,782,107,380,899,676,416,568,393,143,63,459,193,454,392,115,431,536,124,335,86,834,167,85,558,626,725,750,680,557,670,673,447,20,203,936,727,749,416,728,340,430,377,327,300,74,770,602,352,850,653,599,407,537,365,192,168,637,583,377,134,370,563,303,51,123,188,515,697,771,454,67,369,102,683,192,354,575,604,336,290,150,554,137,917,168,732,676,162,490,177,483,560,511,824,97,493,262,422,634,677,123,659,699,379,36,392,246,168,881,912,228,891,253,913,37,754,139,494,406,232,110,807,780,618,544,261,310,780,189,563,479,29,610,891,251,802,539,828,539,455,58,716,487,630,279,602,764,243,778,284,862,270,585,403,302,97,406,307,639,302,437,271,518,633,162,511,815,320,447,703,162,827,328,844,729,399,386,284,402,774,728,379,812,376,62,503,139,902,352,38,357,727,437,508,787,511,543,536,659,493,214,270,165,531,452,832,671,473,179,857,580,342,818,751,468,578,486,447,899,133,295,430,423,674,124,320,612,622,375,681,778,695,223,668,300,464,66,247,129,41,665,704,884,73,658,92,819,176,277,29,663,737,805,26,888,296,376,358,595,813,570,827,701,713,382,663,307,486,162,850,713,732,515,560,349,793,715,205,670,45,489,10,853,244,877,349,280,33,207,645,588,612,590,103,271,162,456,88,915,724,896,230,687,61,910,849,172,312,435,616,596,385,475,775,136,530,373,475,392,913,811,781,797,250,241,320,323,254,123,779,348,734,747,189,203,516,555,844,211,565,759,82,259,724,698,563,34,622,167,915,894,873,249,602,401,656,154,325,91,865,494,589,612,552,375,320,799,750,634,780,305,549,493,444,624,220,674,210,512,490,13,6,14,709,430,518,45,538,857,316,182,617,17,94,710,153,270,264,123,120,372,46,493,618,534,655,446,565,484,589,405,36,131,756,57,183,587,156,204,130,97,559,816,647,632,462,845,66,262,99,522,607,48,742,355,773,367,402,85,581,767,23,839,713,335,607,326,358,603,638,653,541,33,476,240,211,199,833,308,283,475,33,701,787,616,149,760,43,413,787,35,331,596,235,329,469,538,565,706,67,47,306,213,835,48,276,657,322,703,342,111,44,456,427,583,770,608,573,102,536,27,352,392,815,329,539,336,603,368,203,454];